#!/usr/bin/python
# Write Python 3 code in this online editor and run it.
#桶排序 
#桶大小的数组范围一致，即将最大值与最小值间隔进行均分
#再将数组元素依次放到对应的桶内，桶内分到的元素个数不一定一样
def SelectionSort(a):
	n = len(a)
	for i in range(n-1):
		min = i
		for j in range(i+1, n):
			if a[j] < a[min]:
				min = j
		a[i], a[min] = a[min], a[i]
		#print(a)
		
def BucketSort(a):
	minV = min(a)
	maxV = max(a)
	bucketCount = 3
	bucket = [ [], [], []]
	#计算每个桶的数值范围 + bucketCount) // bucketCount 向上取整
	perBucket = (maxV - minV + bucketCount) // bucketCount
	
	#遍历原列表
	for num in a:
		#计算元素所在桶的索引
		bucketIndex = (num - minV) // perBucket
		#元素放入对应桶中
		bucket[bucketIndex].append(num)
		print(bucket)
	
	print("\n")
	#对每个桶单独进行排序
	for i in range(bucketCount):
		SelectionSort(bucket[i])
		
	#排序好的桶依次放回原列表
	idx = 0
	for i in range(bucketCount):
		for v in bucket[i]:
			a[idx] = v
			idx += 1
	print(bucket)
	print(a)
		
if __name__ == '__main__':
	a = [8,7,6,5,4,3,2,1]
	BucketSort(a)
	
'''
[[], [], [8]]
[[], [], [8, 7]]
[[], [6], [8, 7]]
[[], [6, 5], [8, 7]]
[[], [6, 5, 4], [8, 7]]
[[3], [6, 5, 4], [8, 7]]
[[3, 2], [6, 5, 4], [8, 7]]
[[3, 2, 1], [6, 5, 4], [8, 7]]


[[1, 2, 3], [4, 5, 6], [7, 8]]
[1, 2, 3, 4, 5, 6, 7, 8]

'''